#include <vector>
#include <iostream>
#include <unordered_map>
#include <algorithm>

// #1 两数之和

namespace S1 {
    class Solution {
    public:
        std::vector<int> twoSum(std::vector<int>& nums, int target) {
            std::vector<int> res;
            for (int i = 0; i < nums.size(); i++) {
                int n1 = nums[i];
                for (int j = i+ 1; j < nums.size(); j++) {
                    if (target - nums[j] == n1) {
                        res.push_back(i);
                        res.push_back(j);
                    }
                }
            }

            return res;
        }
    };
}

// 这里就是利用哈希表查找O(1)的时间复杂度来提高性能
namespace S2 {
    class Solution {
    public:
        std::vector<int> twoSum(std::vector<int>& nums, int target) {

            // 存储元素的值和下标
            std::unordered_map<int, int> map;
            for (int i = 0; i < nums.size(); i++) {
                int c = target - nums[i];
                if (map.find(c) != map.end()) { // 这里利用哈希表的查找       
                    return {map[c], i};
                } 
                map[nums[i]] = i;
            }

            return {};
        }
    };
}

int main() {
    S1::Solution s;
    std::vector<int> nums {3,2,4};
    auto res = s.twoSum(nums, 6);
    for(auto i : res) {
        std::cout << i << std::endl;
    }
    return 0;
}